#ex1_3
#Ofir Weisse 036928893
#Tomer Sharoni 021761184

import math
import sys


class Normal:
    def __init__( self, angle, start_point, end_point ):
        self.angle = angle
        self.start_point = start_point
        self.end_point = end_point
        
    def __str__( self ):
        return "Normal of line %s->%s is: %f (%f PI)" % \
             ( self.start_point,
               self.end_point,
               self.angle,
               ( self.angle / math.pi ) 
        ) 
        
class Robot:    
    def __init__( self, robot_points ):
        self.__points = robot_points[:]
        self.__build_normal_diagram()
        
        self.reference_point = self.__points[ 0 ]
        
    def __calcNormalAngle( self, start_point, end_point ):
        if start_point.x == end_point.x:
            if end_point.y > start_point.y: #line direction is up
                normal_angle = 0
            else: #line direction is down
                normal_angle = math.pi
            
        else:
            tan_value = ( end_point.y - start_point.y ) / ( end_point.x - start_point.x )
            line_angle = math.atan( tan_value )
            
            if end_point.x < start_point.x: #angle is above pi/2
                line_angle -= math.pi
            
            normal_angle = line_angle - ( math.pi / 2 )
            if normal_angle < 0:
                normal_angle += 2 * math.pi
                
        dbg_msg = "Normal angle for line between %s->%s is: %f (%f PI)" % \
            ( start_point, end_point, normal_angle, ( normal_angle / math.pi ) )
        print( dbg_msg )
        return normal_angle
            
    def __build_normal_diagram ( self ):
        self.__normal_diagram = []
        
        for i in range( 0, len( self.__points ) - 1 ):
            start_point = self.__points[ i ]
            end_point = self.__points[ i + 1 ]
            normal_angle = self.__calcNormalAngle( start_point, end_point )
            
            self.__normal_diagram.append( Normal( normal_angle, start_point, end_point ) )
            
        self.__normal_diagram.sort( key = lambda normal: normal.angle )  
        
        for normal in self.__normal_diagram:
            print( normal )
            
    def __getRobotTouchPointWithEdge( self, original_edge ):
        original_edge_normal_angle = \
            self.__calcNormalAngle( 
                original_edge.start_point,
                original_edge.end_point 
        )
            
        touch_point = None
        
        if original_edge_normal_angle < self.__normal_diagram[ 0 ].angle:
            touch_point = self.__normal_diagram[ 0 ].start_point
            
        else:
            for robot_normal in self.__normal_diagram:
                if original_edge_normal_angle >= robot_normal.angle:
                    touch_point = robot_normal.end_point

        print( "Touch point for edge %s is %s" % ( original_edge, touch_point ) )
        return touch_point
    
    def getTranslationVector( self, original_edge ):
        touch_point = self.__getRobotTouchPointWithEdge( original_edge )
        
        return ( self.reference_point.x - touch_point.x,
                 self.reference_point.y - touch_point.y
        )
        
        
class Point:
    def __init__( self, x, y ):
        self.x = x
        self.y = y
        
    def __str__( self ):
        return "( %f, %f )" % ( self.x, self.y )
        


class Line:
    def __init__( self, start_point, end_point ):
        self.start_point = start_point
        self.end_point = end_point
        
    def __str__( self ):
        return "%s->%s" % ( self.start_point, self.end_point )
    
    def createTranslatedEdge( self, translation_vector ):
        x_movement = translation_vector[ 0 ]
        y_movement = translation_vector[ 1 ]
        start_point = Point( self.start_point.x + x_movement,
                             self.start_point.y + y_movement
        )
        end_point = Point( self.end_point.x + x_movement,
                           self.end_point.y + y_movement
        )
        translated_line = Line( start_point, end_point )
        
        print( "Line %s translated to %s" % ( self, translated_line ) )
        return translated_line
    

    def isPointInsideLine( self, intersection ):
        EPSILON = 0.00001
        
        #ASSUMPTION: intersection point o=is on the infinite line of self
        if intersection.x < min( self.start_point.x, self.end_point.x ) - EPSILON:
            return False
        if intersection.x > max( self.start_point.x, self.end_point.x ) + EPSILON:
            return False
        if intersection.y < min( self.start_point.y, self.end_point.y ) - EPSILON:
            return False
        if intersection.y > max( self.start_point.y, self.end_point.y ) + EPSILON:
            return False
        
        return True
        
    
    def getIntersectionPoint( self, other_line ):
        x_1 = self.start_point.x
        y_1 = self.start_point.y
        x_2 = self.end_point.x
        y_2 = self.end_point.y
        
        x_3 = other_line.start_point.x
        y_3 = other_line.start_point.y
        x_4 = other_line.end_point.x
        y_4 = other_line.end_point.y
        
        denom = float( ( x_1 - x_2 ) * ( y_3 - y_4 ) - ( y_1 - y_2 ) * ( x_3 - x_4 ) )
        x = ( ( x_1 * y_2 - y_1 * x_2 ) * ( x_3 - x_4 ) - ( x_1 - x_2 ) * ( x_3 * y_4 - y_3 * x_4 ) ) / denom
        y = ( ( x_1 * y_2 - y_1 * x_2 ) * ( y_3 - y_4 ) - ( y_1 - y_2 ) * ( x_3 * y_4 - y_3 * x_4 ) ) / denom
        
        intersection = Point( x, y )
        if  not self.isPointInsideLine( intersection ) or \
            not other_line.isPointInsideLine( intersection ):
            intersection = None
            
        dbg_msg = "Intersection of \n" + "\t%s and\n" + "\t%s is\n" + "\t%s" 
        print( dbg_msg % ( self, other_line, intersection ) )
        
        return intersection
    
    def setEndPoint( self, end_point ):
        self.end_point = end_point
        
    def setStartPoint( self, start_point ):
        self.start_point = start_point
        
    def isRightTurn( self, dest_point ):
        self_vector = ( self.end_point.x - self.start_point.x,
                        self.end_point.y - self.start_point.y )
        vector_to_dest = ( dest_point.x - self.end_point.x,
                           dest_point.y - self.end_point.y )
        
        sign = vector_to_dest[ 0 ] * self_vector[ 1 ] - \
                vector_to_dest[ 1 ] * self_vector[ 0 ]
                
        return sign > 0 

class RobotInRoom:
    def __init__( self, input_file_path ):
        data_file = open( input_file_path )
        self.__getRobotPoints( data_file )
        self.__getRoomPoints( data_file )
        self.__robot = Robot( self.__robot_points )
        
    def __getRobotPoints( self, data_file ):
        m = int( data_file.readline() )
        robot_data = map( float, data_file.readline().split() )
        
        self.__robot_points = []
        for i in range( m ):
            self.__robot_points.append( 
                Point( robot_data[ 2 * i ],
                       robot_data[ 2 * i + 1 ] 
                ) 
            )
            
        self.__robot_points.append( self.__robot_points[ 0 ] )#make it cyclic
            
        print( "Robot Points: " )
        for point in self.__robot_points:
            print( point )
    
    def __getRoomPoints( self, data_file ):
        n = int( data_file.readline() )
        room_data = map( float, data_file.readline().split() )
        
        self.__room_points = []
        for i in range( n ):
            self.__room_points.append( 
                Point( room_data[ 2 * i ],
                       room_data[ 2 * i + 1 ] 
                ) 
            )
            
        self.__room_points.append( self.__room_points[ 0 ] )#make it cyclic
         
        print( "Room points:" )
        for point in self.__room_points:
            print( point )
 
    def __getWallsLines( self ):
        room_walls = []
        for i in range( 0, len( self.__room_points ) - 1 ):
            start_point = self.__room_points[ i ]
            end_point = self.__room_points[ i + 1 ]
            room_walls.append( Line( start_point, end_point ) )
            
        return room_walls
    
    def calcFreeSpace( self ):
        room_walls = self.__getWallsLines()
        
        free_space_walls = []
        for original_edge in room_walls:
            translation_vector = \
                self.__robot.getTranslationVector( original_edge )
            new_edge = original_edge.createTranslatedEdge( translation_vector ) 
            
            while True:
                if 0 == len( free_space_walls ):
                    free_space_walls.append( new_edge )
                    break
                
                last_free_space_edge = free_space_walls[ -1 ] #List is necessarily not empty 
                intersection_point = new_edge.getIntersectionPoint( last_free_space_edge )
                
                if intersection_point != None: 
                    print( "Found EASY case!" )
                    #easy case - wall is inside free space:
                    last_free_space_edge.setEndPoint( intersection_point )
                    new_edge.setStartPoint( intersection_point )
                    free_space_walls.append( new_edge )
                    break
                    
                if last_free_space_edge.isRightTurn( new_edge.end_point ):
                    break #New edge does not apear in free space
                    
                free_space_walls.pop()
        
        #Trim first free wall beginning and trim last wall end:
        first_free_space_edge = free_space_walls[ 0 ]
        last_free_space_edge = free_space_walls[ -1 ]
        intersection_point = first_free_space_edge.getIntersectionPoint( last_free_space_edge )
        last_free_space_edge.setEndPoint( intersection_point )
        first_free_space_edge.setStartPoint( intersection_point )
        
        
        return free_space_walls
    
    def getRoomPoints( self ):
        return self.__room_points
    
    def getRobotPoints( self ):
        return self.__robot_points

def generate_free_space_script( free_space ):
    script = "%plot free space:\n"
    
    x_coordinates = "x = [ "
    y_coordinates = "y = [ "
    
    xs = map( lambda wall: wall.start_point.x, free_space )
    ys = map( lambda wall: wall.start_point.y, free_space )
    
    x_coordinates += " ".join( map( str, xs ) )
    x_coordinates += " " + str( xs[ 0 ] )
    x_coordinates += " ] ;"
    
    y_coordinates += " ".join( map( str, ys ) )
    y_coordinates += " " + str( ys[ 0 ] )
    y_coordinates += " ] ;"

    script += x_coordinates + "\n"
    script += y_coordinates + "\n"
    script += "hold on\n"
    script += "plot( x,y )\n"
#    script += "xlim( [%f %f ] )\n" % ( min( xs ) - 1, max( xs ) + 1 )
#    script += "ylim( [%f %f ] )\n" % ( min( ys ) - 1, max( ys ) + 1 )
    
    return script



def generate_room_script( room_points ):
    script = "%plot room:\n"
    
    x_coordinates = "x = [ "
    y_coordinates = "y = [ "
    
    xs = map( lambda point: point.x, room_points )
    ys = map( lambda point: point.y, room_points )
    
    x_coordinates += " ".join( map( str, xs ) )
    x_coordinates += " " + str( xs[ 0 ] )
    x_coordinates += " ] ;"
    
    y_coordinates += " ".join( map( str, ys ) )
    y_coordinates += " " + str( ys[ 0 ] )
    y_coordinates += " ] ;"

    script += x_coordinates + "\n"
    script += y_coordinates + "\n"
    script += "hold on\n"
    script += "plot( x,y, 'r' )\n"
    script += "xlim( [%f %f ] )\n" % ( min( xs ) - 1, max( xs ) + 1 )
    script += "ylim( [%f %f ] )\n" % ( min( ys ) - 1, max( ys ) + 1 )
    
    return script



def generate_roobot_script( robot_points ):
    script = "%plot robot:\n"
    
    x_coordinates = "x = [ "
    y_coordinates = "y = [ "
    
    xs = map( lambda point: point.x, robot_points )
    ys = map( lambda point: point.y, robot_points )
    
    x_coordinates += " ".join( map( str, xs ) )
    x_coordinates += " " + str( xs[ 0 ] )
    x_coordinates += " ] ;"
    
    y_coordinates += " ".join( map( str, ys ) )
    y_coordinates += " " + str( ys[ 0 ] )
    y_coordinates += " ] ;"

    script += x_coordinates + "\n"
    script += y_coordinates + "\n"
    script += "hold on\n"
    script += "plot( x,y, 'g' )\n"
    script += "hold on\n"
    script += "%show reference point:\n"
    script += "plot( %f,%f, 'xg' )\n" % ( robot_points[ 0 ].x, robot_points[ 0 ].y )
    
    
    
    return script


def generate_matlab_plot( robot_in_room, free_space ):
    script = "close all\n"
    script += "figure\n"
    script += generate_free_space_script( free_space )
    script += generate_roobot_script( robot_in_room.getRobotPoints() )
    script += generate_room_script( robot_in_room.getRoomPoints() )
     
    return script

def main():
    if len( sys.argv ) < 3:
        print( "\n\nUsage: python free_space.py input_file_name output_file_name\n\n" )

    else:
        robot_in_room = RobotInRoom( sys.argv[1] )
        free_space = robot_in_room.calcFreeSpace()
        
        p = str(len(free_space)) + "\n"
        for wall in free_space:
            p += str(wall.start_point.x)
            p += " "
            p += str(wall.start_point.y)
            p += " "
        
        f = open( sys.argv[2], "w" )
        f.write( p )
        f.close()

        #matlab_plot = generate_matlab_plot( robot_in_room, free_space )
        #
        #f = open( "show_free_space.m", "w" )
        #f.write( matlab_plot )
        #f.close()

if __name__ == "__main__":
    main()
    
